//给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。 
//
// 算法的时间复杂度应该为 O(log (m+n)) 。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums1 = [1,3], nums2 = [2]
//输出：2.00000
//解释：合并数组 = [1,2,3] ，中位数 2
// 
//
// 示例 2： 
//
// 
//输入：nums1 = [1,2], nums2 = [3,4]
//输出：2.50000
//解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
// 
//
// 
//
// 
//
// 提示： 
//
// 
// nums1.length == m 
// nums2.length == n 
// 0 <= m <= 1000 
// 0 <= n <= 1000 
// 1 <= m + n <= 2000 
// -10⁶ <= nums1[i], nums2[i] <= 10⁶ 
// 
//
// Related Topics 数组 二分查找 分治 👍 6525 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
// class Solution4 {
//     public double findMedianSortedArrays(int[] nums1, int[] nums2) {
//         int i = 0;
//         int j = 0;
//         int N = nums1.length + nums2.length;
//         int k = N / 2;
//         int pre = Integer.MAX_VALUE;
//         int curr = Integer.MAX_VALUE;
//         for (int p = 0; p <= k; p++) {
//             pre = curr;
//             int n1 = i < nums1.length ? nums1[i] : Integer.MAX_VALUE;
//             int n2 = j < nums2.length ? nums2[j] : Integer.MAX_VALUE;
//             if (n1 < n2) {
//                 curr = n1;
//                 i++;
//             } else {
//                 curr = n2;
//                 j++;
//             }
//         }
//
//         if (N % 2 == 0) {
//             return (pre + curr) / 2.0;
//         } else {
//             return curr;
//         }
//     }
// }

/*
 [?, ?, 4, ?, ...]
 [?, ?, 6, ?, ...]
 数组长度和为 7, 结果等价转换为求第 7小的数
 数组1和数组2, 第一轮, 取第3
 为什么 7/2 就可以.
 反证, 如果第7小在数组1 4 所在位置前, 那么数组2 6 所在位置至少要<=4
 */
class Solution4_2 {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int N1 = nums1.length, N2 = nums2.length;
        int totalLen = N1 + N2;
        int left = (totalLen - 1) / 2;
        int right = (totalLen) / 2;

        if (left == right) {
            // 奇数, 取第 left 位, 一次即可
            return getKth(nums1, 0, N1 - 1, nums2, 0, N2 - 1, left);
        } else {
            return (getKth(nums1, 0, N1 - 1, nums2, 0, N2 - 1, left)
                            + getKth(nums1, 0, N1 - 1, nums2, 0, N2 - 1, right)
            ) * 0.5;
        }
    }

    // 两个升序数组, 取第 k 位数(从0开始)
    private int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
        if (start1 > end1 && start2 > end2) {
            return -1;
        } else if (start1 > end1) {
            return nums2[start2 + k];
        } else if (start2 > end2) {
            return nums1[start1 + k];
        }

        if (k == 0) {
            return nums1[start1] < nums2[start2] ? nums1[start1] : nums2[start2];
        }

        int i = Math.min(start1 + ((k-1) / 2), end1);
        int j = Math.min(start2 + ((k-1) / 2), end2);

        if (nums1[i] < nums2[j]) {
            return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
        } else {
            return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
        }
    }
}

//leetcode submit region end(Prohibit modification and deletion)

class Test4 {
    public static void main(String[] args) {
        int[] nums1 = new int[]{1, 3};
        int[] nums2 = new int[]{2, 7};
        // double res = new Solution().findMedianSortedArrays(nums1, nums2);
        // System.out.println(res);
    }
}